In modern packet data networks, traffic is routed, hop-by-hop between a source node and a destination node, using a path that is computed and allocated in advance. Typically, computation of the path is based on a set of constrains. For example, the path may require allocation of a particular minimum bandwidth, or quality of service (QOS). With this arrangement, links in the path can be rejected or allocated to the path, based on whether or not they can satisfy the defined constraints. Typical path constraints may, for example, include bandwidth, Quality of Service (QoS), and latency (i.e. message wait times).
Typically, computation of a path is based on network topology information that is gathered by each node. Such topology information is normally distributed within a network (or portion thereof) by way of Link State Advertisement (LSA) messages that are flooded by each node. Thus, each node uses received LSAs to construct a network topology database covering at least the node's nearest neighbour nodes within the network. Subsequently, when a path set-up message is received by the node, a Dijkstra algorithm can be implemented to use the topology data base to select the optimal link for the next hop in the path. The link identifier can then be added to the path set-up message, which is then forwarded through the link to the next node in the path. By this means, a path can be set up, hop-by-hop through the network.
This arrangement suffers a number of disadvantages. For example, as the size of the network grows, so too must the size of the topology database maintained by each node. For very large networks, this requirement can place a heavy burden on the node's resources, and increases the time required to search the database to find a route (i.e. select the next link) that satisfies the constraints.
An additional limitation of this approach is that it cannot readily accommodate intransitive constraints within the network. For example, consider three nodes A, B and C, connected together by pair of links A-B and B-C, as shown in FIG. 1. Conventional constraint-based routing algorithms assume that all path and network constraints are transitive. Thus, if both links A-B and B-C satisfy the path constraints, then the combined path A-B-C, formed by concatenating the two links via node B, will also satisfy the path constraints. However, in the case of intransitive constraints this assumption may not, in fact, be true.
For example, consider the case of a photonic network, in which node B is a photonic (that is, all-optical) switch. Each link A-B and B-C, taken alone, may satisfy all constraints, and may thus be usable. However, concatenating the two links together through (photonic) node B, to form path A-B-C, may exceed the permissible optical signal reach (e.g. due to dispersion), which would violate a network constraint and thus not be permitted. Another example involves the routing of traffic through node B, between link A-B and link B-C. Conventional routing protocols assume that node B (and every other node, for that matter) is able to map every input port to any output port, so that the required routing of traffic through node B is inherently possible. However, in a network that implements a form of time division multiplexing, node B may not, in fact, be able to route traffic from link A-B to link B-C. An example of this situation would be a case where links A-B and B-C support different sets of timeslots. In such a case, it may not be possible to route traffic from link A-B to link B-C, because they share no common free timeslot. This is a common problem on SONET rings, where timeslots must be unchanged during traversal of all segments on the ring.
Conventional constraint-based routing protocols can deal with intransitive constraints such as those described above, but only by compounding the size and complexity of the topology database. In particular, the topology database must be expanded to include, in addition to information on each link, information regarding each intra-node route between the links hosted by each node. For a network (or network region) having N links, this increases the size of the topology database by about N2 entries. As the size of the network (i.e. number of links N) increases, the size of the topology database and volume of LSA messaging rapidly become unmanageable.
Accordingly, techniques for constraint-based routing in a large network having intransitive constraints remains highly desirable.